home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Add-Ons / MPW / MPW noweb 2.7 / src / c / recognize.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-30  |  5.6 KB  |  212 lines  |  [TEXT/MPS ]
  1. #line 35 "recognize.nw"
  2. #include <string.h>
  3. #line 38 "recognize.nw"
  4. #include <stdlib.h>
  5. #line 53 "recognize.nw"
  6. typedef struct recognizer *Recognizer;
  7. #line 69 "recognize.nw"
  8. typedef void (*Callback) (void *closure, char *id, char *instance);
  9. #line 50 "recognize.nw"
  10. Recognizer new_recognizer(char *alphanum, char *symbols);
  11. #line 59 "recognize.nw"
  12. void add_ident(Recognizer r, char *id);
  13. void stop_adding(Recognizer r);
  14. #line 63 "recognize.nw"
  15. void search_for_ident(Recognizer r, char *input, Callback f, void *closure);
  16. #line 77 "recognize.nw"
  17. typedef struct goto_node Goto_Node;
  18. typedef struct move_node Move_Node;
  19. #line 81 "recognize.nw"
  20. typedef struct name_node {
  21.   struct name_node *next; /* points to the next name on the output list */
  22.   char *name;
  23. } Name_Node;
  24. #line 87 "recognize.nw"
  25. struct move_node {
  26.   Move_Node *next;      /* points to the next node on the move list */
  27.   Goto_Node *state;     /* the next state for this character */
  28.   char c;
  29. };
  30. #line 94 "recognize.nw"
  31. struct goto_node {
  32.   Name_Node *output;    /* list of words ending in this state */
  33.   Move_Node *moves;     /* list of possible moves */
  34.   Goto_Node *fail;      /* and where to go when no move fits */
  35.   Goto_Node *next;      /* next goto node with same depth */
  36. };
  37. #line 102 "recognize.nw"
  38. struct recognizer {
  39.   Goto_Node *root[128]; /* might want 256, depending on the character set */
  40.   char *alphas;
  41.   char *syms;
  42.   int max_depth;
  43.   Goto_Node **depths; /* an array, max_depth long, of lists of goto_nodes,
  44.                          created while adding ids, used while building
  45.                          the failure functions */
  46. };
  47. #line 329 "recognize.nw"
  48. int reject_match(Recognizer r, char *id, char *input, char *current);
  49. #line 120 "recognize.nw"
  50. static Goto_Node *goto_lookup(char c, Goto_Node *g)
  51. {
  52.   Move_Node *m = g->moves;
  53.   while (m && m->c != c)
  54.     m = m->next;
  55.   return m ? m->state : NULL;
  56. }
  57. #line 134 "recognize.nw"
  58. Recognizer new_recognizer(char *alphanum, char *symbols)
  59. {
  60.   Recognizer r = (Recognizer) calloc(1, sizeof(struct recognizer));
  61.   r->alphas = alphanum;
  62.   r->syms = symbols;
  63.   r->max_depth = 10;
  64.   r->depths = (Goto_Node **) calloc(r->max_depth, sizeof(Goto_Node *));
  65.   return r;
  66. }
  67. #line 150 "recognize.nw"
  68. void add_ident(Recognizer r, char *id)
  69. {
  70.   int depth = 2;
  71.   char *p = id;
  72.   char c = *p++;
  73.   Goto_Node *q = r->root[c];
  74.   if (!q) 
  75.     
  76. #line 171 "recognize.nw"
  77. {
  78.   q = (Goto_Node *) calloc(1, sizeof(Goto_Node));
  79.   r->root[c] = q;
  80.   q->next = r->depths[1];
  81.   r->depths[1] = q;
  82. }
  83. #line 158 "recognize.nw"
  84.   c = *p++;
  85.   while (c) {
  86.     Goto_Node *new = goto_lookup(c, q);
  87.     if (!new)
  88.       
  89. #line 178 "recognize.nw"
  90. {
  91.   Move_Node *new_move = (Move_Node *) malloc(sizeof(Move_Node));
  92.   new = (Goto_Node *) calloc(1, sizeof(Goto_Node));
  93.   new_move->state = new;
  94.   new_move->c = c;
  95.   new_move->next = q->moves;
  96.   q->moves = new_move;
  97.   if (depth == r->max_depth)
  98.     
  99. #line 191 "recognize.nw"
  100. {
  101.   int i;
  102.   Goto_Node **new_depths = (Goto_Node **) calloc(2*depth, sizeof(Goto_Node *));
  103.   r->max_depth = 2 * depth;
  104.   for (i=0; i<depth; i++)
  105.     new_depths[i] = r->depths[i];
  106.   free(r->depths);
  107.   r->depths = new_depths;
  108. }
  109. #line 187 "recognize.nw"
  110.   new->next = r->depths[depth];
  111.   r->depths[depth] = new;
  112. }
  113. #line 163 "recognize.nw"
  114.     q = new;
  115.     depth++;
  116.     c = *p++;
  117.   }
  118.   
  119. #line 201 "recognize.nw"
  120. if (!q->output) {
  121.   char *copy = malloc(strlen(id) + 1);
  122.   strcpy(copy, id);
  123.   q->output = (Name_Node *) malloc(sizeof(Name_Node));
  124.   q->output->next = NULL;
  125.   q->output->name = copy;
  126. }
  127. #line 168 "recognize.nw"
  128. }
  129. #line 217 "recognize.nw"
  130. void stop_adding(Recognizer r)
  131. {
  132.   int depth;
  133.   for (depth=1; depth<r->max_depth; depth++) {
  134.     Goto_Node *g = r->depths[depth];
  135.     while (g) {
  136.       Move_Node *m = g->moves;
  137.       while (m) {
  138.         char a = m->c;
  139.         Goto_Node *s = m->state;
  140.         Goto_Node *state = g->fail;
  141.         while (state && !goto_lookup(a, state))
  142.           state = state->fail;
  143.         if (state)
  144.           s->fail = goto_lookup(a, state);
  145.         else
  146.           s->fail = r->root[a];
  147.         if (s->fail) {
  148.           Name_Node *p = s->fail->output;
  149.           while (p) {
  150.             Name_Node *q = (Name_Node *) malloc(sizeof(Name_Node));
  151.             q->name = p->name; /* depending on memory deallocation 
  152.                                   strategy, we may need to copy this */
  153.             q->next = s->output;
  154.             s->output = q;
  155.             p = p->next;
  156.           }
  157.         }
  158.         m = m->next;
  159.       }
  160.       g = g->next;
  161.     }
  162.   }
  163. }
  164. #line 257 "recognize.nw"
  165. void search_for_ident(Recognizer r, char *input, Callback f, void *closure)
  166. {
  167.   Goto_Node *state = NULL;
  168.   char *current = input;
  169.   char c = *current++;
  170.   while (c) {
  171.     
  172. #line 274 "recognize.nw"
  173. {
  174.   while (state && !goto_lookup(c, state))
  175.     state = state->fail;
  176.   state = state ? goto_lookup(c, state) : r->root[c];
  177. }
  178. #line 264 "recognize.nw"
  179.     
  180. #line 284 "recognize.nw"
  181. {
  182.   if (state) {
  183.     Name_Node *p = state->output;
  184.     while (p) {
  185.       if (!reject_match(r, p->name, input, current))
  186.         f(closure, p->name, current - strlen(p->name));
  187.       p = p->next;
  188.     }
  189.   }
  190. }
  191. #line 265 "recognize.nw"
  192.     c = *current++;
  193.   }
  194. }
  195. #line 308 "recognize.nw"
  196. int reject_match(Recognizer r, char *id, char *input, char *current)
  197. {
  198.   int len = strlen(id);
  199.   char first = id[0];
  200.   char last = id[len - 1];
  201.   char next = *current;
  202.   char prev = '\0';
  203.   current = current - len - 1;
  204.   if (input <= current)
  205.     prev = *current;
  206.   if (strchr(r->alphas, first) && strchr(r->alphas, prev)) return 1;
  207.   if (strchr(r->alphas, last ) && strchr(r->alphas, next)) return 1;
  208.   if (strchr(r->syms,   first) && strchr(r->syms,   prev)) return 1;
  209.   if (strchr(r->syms,   last ) && strchr(r->syms,   next)) return 1;
  210.   return 0;
  211. }
  212.